The growth in electronic commerce systems has led to a rapid growth in the number of financial transactions taking place across electronic networks. Micropayments enable new forms of electronic commerce transactions, by providing a convenient method for financing on-line low-value services such as information retrieval services. Micropayments may have very low value—in some cases fractions of a penny—but may be executed in very high volumes. By way of example, information service providers may wish to charge for their services in small increments. Micropayments may be used to pay for each web page visited or for each minute of music or video streamed to the user.
A simple form of an electronic payment scheme is an electronic check. An electronic check consists of a check that is digitally signed, rather than hand-signed. A digital signature allows the receiver of the check to verify both the authenticity of the signing party, and the integrity of the contents of the check (e.g., the date and amount of the check). The literature on public key cryptography provides many methods for implementing digital signatures, such as the RSA method described in “A method for obtaining digital signatures and public-key cryptosystems,” Rivest, R. L., Shamir, A., and Adleman, L. A., Communications of the ACM, Vol. 21, No. 2, 1978, S. 120-126. As is well known, each party in a public key cryptosystem uses a unique pair of keys. Each pair includes a public key and a corresponding private (or secret) key. While the public key is made available to the public, the corresponding private key is known and accessible only to the owner, who safeguards it and keeps it secret. It is not computationally feasible to derive the private key from the knowledge or discovery of the corresponding public key. Therefore, making a public key available to the public does not endanger the security of the matching private key. Because a private key is never accessible to anyone but its owner, public key cryptosystems enjoy an increased security, as compared to systems in which secret keys are shared among different parties.
In a public key cryptosystem, a sender who wishes to secretly send a message obtains the receiver's public key and uses it to encrypt the message. Upon receiving the encrypted message, the receiver uses his matching private key to decrypt it and read the original message. Without access to the matching private key, it is computationally infeasible to decrypt the encrypted message.
In a public key digital signature scheme, a signer of a message creates his digital signature by applying his private key to the message. The resulting digital signature is thus unique to both the message and to the particular private key used to create the digital signature. Anyone in possession of the message and the digital signature can verify the authenticity of the digital signature using the signer's public key.
A hash function is also used in many public key digital signature schemes. A hash function is an algorithm which, when applied to a message, creates a digital “fingerprint” of the message, in the form of a “hash value” that typically has a fixed length. A “one-way collision-resistant” (or secure) hash function is a hash function for which it is computationally infeasible to derive the original message from its hash value, or even to find two messages having the same hash value. The hash of a message thus works well as an identifying “fingerprint” for the message, since if one makes any change, even the slightest change, to a message, one invariably obtains a message with a different hash value.
It is common to use hash functions in digital signature schemes in a “hash and sign” manner. To create a digital signature in this way, the sender of a message applies a hash function to the message, thus computing a message digest or hash value for the message. The sender then applies his private key to the hash value to obtain his digital signature for that message.
The authenticity of the digital signature, as well as the integrity of the contents of the message, can be verified using the sender's public key and the hash function that was used to create the signature. The receiver can verify that the message was indeed signed by the sender by recomputing the hash value for the message, and then applying a verification procedure that takes as inputs this hash value and the sender's public key. The verification procedure might say, for example, to use the sender's public key as a decryption key and to accept the signature as valid if the decryption yields the recomputed hash value of the message. If verification succeeds, the receiver may be confident that the sender actually signed the message and that the message was not altered since it was signed.
In a typical electronic check payment scheme, a user pays a merchant for a transaction by providing a digital signature to a piece of data that identifies the transaction. The data may identify, among other things, the user, the user's bank account number, the merchant, the amount to be paid, the time of the transaction, and/or the information, services, or merchandise that has been purchased. Typically, the merchant deposits the electronic check that he receives from the user by sending the check to the bank.
The digital signature capabilities in an electronic check scheme may be supported by digital certificates. A digital certificate is most commonly an electronic document that asserts that a particular individual holds the private key corresponding to the public key given in the certificate. In other words, the certificate correlates a key pair with a particular party. Since the certificate is itself digitally signed by a trusted authority, a digital certificate is normally trusted as proof that the named party indeed owns the public key listed in the certificate and that the named party exclusively controls the corresponding private key. Digital certificates may also assert that the party is authorized to sign electronic payments or perform other specified actions.
After verifying the digital signature on an electronic check, the bank may credit the merchant with an appropriate amount, and may debit the user with an appropriate amount. The bank may also charge discretionary transaction fees or other fees.
Electronic payment systems, and in particular micropayment systems, face many challenges. A fundamental problem with micropayments lies in a bank's processing costs for the micropayments. Frequently, the cost to the bank of handling a micropayment transaction will be many times larger than the value of the micropayment itself. For example, processing a credit card transaction usually costs about 25 cents, while a typical micropayment may be worth about 1 cent or less. Exceptional efficiency is therefore required in order to support micropayments; otherwise the cost of the payment mechanism will much exceed the value of the payments.
Micropayment schemes therefore attempt to reduce the bank's processing costs by aggregating many small payments into fewer, larger payments. A variety of aggregation strategies are available. Some micropayment schemes have session-level aggregation: all payments between a user and a merchant during a given “session” are aggregated into a single larger payment. Another strategy is global aggregation: payments are aggregated across all user/merchant pairs. Global aggregation can provide greater flexibility and greater cost savings.
A number of micropayment schemes are known in the art, and surveys can be found in the literature, for example in “Digital Cash: Commerce on the Net,” Peter Wayner, Academic Press, 1996. Micropayment schemes that are currently known include “PayWord” (described in “PayWord and MicroMint: Two simple micropayment schemes,” Ronald L. Rivest and Adi Shamir, Fourth Cambridge Workshop on Security Protocols, Springer Verlag April 1996), and the “electronic lottery scheme” (described in “Electronic Lottery Tickets as Micropayments,” Ronald L. Rivest, in Proceedings of Financial Cryptography '97, vol. 1318 of Lecture Notes in Computer Science, pp. 307-314, Springer 1997). Other known micropayment schemes include, but are not limited to, “Millicent” by Manasse et al., “MicroMint” by Rivest and Shamir, “NetCard” by Anderson, “PayTree” by Jutla and Yung, “MicroiKP” by Hauser et al., the probabilistic polling scheme by Jarecki and Odlyzko, a proposal for “transactions using bets” by Wheeler, a similar proposal by Pedersen, and a related proposal for micropayments by efficient coin-flipping, by Lipton and Ostrovsky. The Jarecki/Odlyzko probabilistic polling scheme is disclosed in U.S. Pat. No. 5,999,919, entitled “Efficient Micropayment System,” and issued to Stanislaw Jarecki and Andrew M. Odlyzko on Dec. 7, 1999.
PayWord is a micropayment system based on public key digital signature schemes and one-way hash-functions. In the PayWord system, a user receives from a bank a digital certificate, which authorizes the user to make chains of hash values, or “paywords” wi. These paywords can be monetarily redeemed from the bank by the merchant. The i-th payword is related to the i+1-th payword by the relation:wi=h(wi+i),where h is a one-way hash function. Thus it is computationally infeasible to derive wi+1 from h(wi+i). The i+1-st payword wi+1 can be verified by the merchant using the i-th payword, by performing the hash operation h on wi+1. In the PayWord scheme, the user computes a chain of hash values, w0, w1, . . . , wn, and commits to the entire chain by sending his digital signature of the root w0 to the merchant. Afterwards, the user makes each successive payment to the merchant by revealing the paywords consecutively in turn (w1, w2, . . . , wi, . . . ). Each consecutive value in the chain can be verified by the merchant, by performing the hash function on that value in order to check that it hashed to the previous value in the payword chain.
PayWord allows the merchant to conveniently aggregate the buyer's payments. After k micropayments have been made, if the merchant feels that, taken together, the k micropayments constitute a sizable enough macropayment, the merchant makes a single deposit in the bank for k cents (or other appropriate monetary units that represents each micropayment). The vendor reports to the bank only two values, wk, and the user's signature of w0. The bank verifies the user's signature of w0, and iterates the hash function k times on wk, to verify that this operation does indeed yield w0. After verification, the bank pays k cents into vendor's account, and charges the user's account k cents, and charge other transaction fees at its discretion.
PayWord suffers from the disadvantage that the merchant cannot aggregate micropayments of different users. This is because in PayWord, each user must establish his own hash-value chain with the merchant, and because different hash-value chains cannot be merged. Many other micropayment proposals, such as Millicent, also suffer from this problem of not being able to aggregate micropayments across different user/merchant pairs. That is, PayWord only provides session-level aggregation, not global aggregation.
The electronic lottery scheme by Rivest provides another method for aggregating micropayments, so as to reduce transaction costs. This scheme is based on a selection rate or selection probability s (0<s<1) for each micropayment: on average, only one out of every 1/s micropayments is selected for actual payment. The selection rate s is known, predictable, and fixed. For each micropayment presented to the merchant, the merchant first verifies the user's signature on the root w0 of the PayWord chain and verifies that the provided hash value wk indeed yields w0 when iteratively hashed k times. If so, the merchant accepts the micropayment from the user. The merchant then goes through a predetermined interaction protocol with the user, in order to determine whether or not the micropayment should be selected for deposit at the bank. A non-selected check can not be deposited and is thus worthless to the merchant; it is thus discarded by the merchant. Only a micropayment that is selected (through the interaction protocol) is actually presented to the bank by the merchant, in order to receive payment. In this way, the bank does not have to process each and every micropayment, but only processes, on average, one out of 1/s micropayments. The bank's processing costs are thereby greatly reduced. To make this process fair to the merchant, for each selected micropayment, the merchant gets paid an amount 1/s times greater than the originally specified micropayment amount. In other words, the bank pays to the merchant an amount that is “scaled” to a value 1/s times the face value of the micropayment.
Despite its advantages, the electronic lottery scheme suffers from the drawback that the user and the merchant must interact for each micropayment, in order to determine whether a particular micropayment should be selected for deposit. This requirement considerably slows down the electronic payment system, and in some cases renders the scheme impracticable.
For the foregoing reasons, there is a need for a non-interactive micropayment method and system, which allow global aggregation of micropayments to minimize bank processing costs, but which at the same time do not require user-merchant interaction in the micropayment selection process.
In addition, it is desirable to incorporate time constraints into a micropayment system. For example, it would be advantageous to include in a micropayment system time constraints that require the merchant to deposit any payable check (i.e. a micropayment that is properly selected for deposit) in the bank within a reasonable time period, in order to receive payment from the bank. In this way, the user would not be charged too late, i.e. when a possible expenditure for the transaction is no longer in his budget. This type of constraint would also give an extra incentive to the merchant to verify that the time information on a check C is accurate, thereby enhancing the security of the system.
Another problem inherent in probabilistic micropayment schemes, besides the inefficiency caused by user-merchant interaction in the selection process, is the risk to the user of being charged in excess of what he actually spends. A user in a probabilistic micropayment scheme must deal with the probability (albeit small) that in some cases, by bad luck, he may have to pay more than what he actually spent. Such occurrences may be rare, and the relative impact of such a rare occurrence may decrease dramatically with the number of micropayments made. Nonetheless, the possibility, however slim, of being excessively charged may constitute a strong obstacle to a widespread acceptance of the scheme. This is because ordinary users are generally not accustomed to managing risk.
For the foregoing reasons, there is a need for a micropayment method and system, which not only minimizes bank processing costs, but also guarantee that the user is never charged in excess of what he actually spends.
Finally, micropayment systems which attempt to increase their efficiency generally call the bank into action only with respect to those payments that have been selected for payment by the merchant, and that generally constitute only a small fraction of the total number of payments. Such micropayment systems, however, do not provide the bank with any flexibility or control over the payment selection process. Such control may be advantageous to the bank in managing its risk.
It is therefore desirable that a micropayment scheme be available which not only eliminates the need for user-merchant interaction in the selection process, and shifts the risk of excessive payment away from the user to the bank or the merchant, but also provides the bank with some flexibility and control over the payment selection process.